#include"图书信息管理系统.h"

void Swap(ElemType* a, ElemType* b)//交换
{
	ElemType tmp = *a;
	*a = *b;
	*b = tmp;
}

// 创建返回链表的头结点
ListNode* ListCreate()
{
	ElemType x = { -668,"分类","书名","作者","出版社",0,-1 };//初始化头节点的所有信息
	ListNode* newnode = ListNewNode(x);//调用节点创建函数创建节点
	newnode->prev = newnode;//头节点的指针指向自己
	newnode->next = newnode;
	return newnode;//返回头节点
}

//读取文件
void ReadFiles(ListNode* pHead)
{
	assert(pHead);
	FILE* fail = fopen("./Book.txt", "r");//以只读的方式打开文件
	if (!fail)//检查文件是否打开成功
	{
		perror("Open Fail Error!\n");//不成功报错并退出
		exit(EOF);
	}
	fgets(Title, 100, fail);//读取标题
	ElemType x;
	while (fscanf(fail, "%d%s%s%s%s%d%f", &(x.ID), x.Class, x.BookName, x.Author, x.Publishing, &(x.Count), &(x.Price)) != EOF)
	{
		ListInsert(pHead->next, x);
		++(pHead->data.Count);
	}
	fclose(fail);
}

//写入文件
void WriteFail(ListNode* pHead)
{
	assert(pHead);
	FILE* fail = fopen("./Book.txt", "w");//以只写的方式打开文件
	if (!fail)//检查文件是否打开成功
	{
		perror("Open Fail Error!\n");//不成功报错并退出
		exit(EOF);
	}
	fputs(Title,fail);//写入标题
    ListNode* cur = NULL;
	for (cur = pHead->prev; cur != pHead; cur = cur->prev)
	{
		fprintf(fail, "%-6d %-10s %-20s %-10s %-30s %-6d %-2.2f\n", cur->data.ID, cur->data.Class, cur->data.BookName, cur->data.Author, cur->data.Publishing, cur->data.Count, cur->data.Price);
	}
	fclose(fail);
}

//双向链表新节点的申请
ListNode* ListNewNode(ElemType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (!newnode)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;//将打包的结构体数据赋值给data域
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

//双链表链表空的检查
bool ListEmpty(ListNode* pHead)
{
	return (pHead->prev == pHead->next) && (pHead->next == pHead) ? false : true;//如果前驱等于后继等于自己表示空
}

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);//节点为空则报错
	if (pHead)
	{
		printf("\t\t\t\t\t*图书信息管理系统*\n");
		printf("-----------------------------------------------------------------------------------------------\n");
		printf("%s\n", Title);
		int i = 0;
        ListNode* cur = NULL;
		for (cur = pHead->prev; cur != pHead; cur = cur->prev)
		{
			printf("%-6d %-10s %-20s %-10s %-30s %-6d %-2.2f\n", cur->data.ID, cur->data.Class, cur->data.BookName, cur->data.Author, cur->data.Publishing, cur->data.Count, cur->data.Price);
		}
		printf("----------------------------------------共%d本图书信息-----------------------------------------\n", (pHead->data.Count));
	}
	else
	{
		perror("Guard Error\n");
	}
}

// 双向链表在pos的前面进行插入(相当于在当前位置插入)
void ListInsert(ListNode* pos, ElemType x)
{
	if (pos)//pos不为空说明找到了
	{
		ListNode* newnode = ListNewNode(x);//申请新节点
		newnode->prev = pos->prev;//新节点的前驱指向pos节点的前驱
		newnode->next = pos;//新节点的后继等于pos
		pos->prev->next = newnode;//pos的前驱的后继节点指向新节点
		pos->prev = newnode;//pos前驱指向新节点
	}
	else
	{
		printf("没有此位置！\n");
	}
}

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	if (pos)
	{
		ListNode* posprev = pos->prev;
		ListNode* posnext = pos->next;
		posnext->prev = posprev;
		posprev->next = posnext;
		free(pos);
	}
	else
	{
		printf("位置错误或链表为空!\n");
	}
}

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
    ListNode* cur = NULL,*curnext = NULL;
	for (cur = pHead->next, curnext = cur->next; cur != pHead; cur = curnext, curnext = cur->next)
	{
		free(cur);
	}
	free(pHead);
}

// 双向链表查找-核心代码
ListNode* ListFind(ListNode* pHead,ListNode* pos,char* value)
{
	assert(pHead);
	if (pos&&pHead)
	{
        ListNode* cur = NULL;
		for (cur = pos->next; cur != pHead; cur = cur->next)
		{
			//对比分类-书名-作者-出版社
			if (strcmp(cur->data.Class, value) == 0 || strcmp(cur->data.BookName, value) == 0 || strcmp(cur->data.Author, value) == 0 || strcmp(cur->data.Publishing, value) == 0)
			{
				return cur;
			}
		}
	}
	return NULL;
}

//查找并输出
void FindOutPut(ListNode* pHead,char* value)
{
	ListNode* cur = pHead;
	printf("------------------------------------------查找结果--------------------------------------------\n");
	printf("%s\n", Title);
	int i = 0;
	while (cur)
	{
		cur = ListFind(pHead, cur, value);
		if (cur)
		{
			printf("%-6d %-10s %-20s %-10s %-30s %-6d %-2.2f\n", cur->data.ID, cur->data.Class, cur->data.BookName, cur->data.Author, cur->data.Publishing, cur->data.Count, cur->data.Price);
			++i;
		}
	}
	printf("----------------------------------------共%d本图书信息-----------------------------------------\n", i);
}

void InsertBook(ListNode* pHead)//插入书籍
{
InsertAdd:
	system("cls");//清空屏幕
	ListPrint(pHead);
	printf("请输入插入位置的书籍编号>");
	int position = -1;
	scanf("%d", &position);
	ListNode* insertpos = NULL;
    ListNode* cur = NULL;
	for (cur = pHead->prev; cur != pHead; cur = cur->prev)//查找编号
	{
		if (cur->data.ID == position)
		{
			insertpos = cur;
			break;
		}
	}

	if (!insertpos)//检查编号是否存在-不存在开始分情况讨论
	{
		printf("编号不存在!\n");
POS:
		printf("(1)重新选择编号位置添加\n(2)添加在当前信息的最末尾\n(0)放弃添加\n");
		printf("请选择>");
		int order = 0;
		scanf("%d", &order);
		if (order == 1)
		{
			system("cls");//清空屏幕
			goto InsertAdd;
		}
		else if (order == 2)
		{
			insertpos = pHead->next;//给表尾位置
		}
		else if(order == 0)
		{
			return;
		}
		else
		{
			system("cls");//清空屏幕
			printf("选择错误!请重新选择!\n");
			goto POS;//输入错误重新开始
		}
		
	}

	ElemType value;
	printf("------------------------------------------添加图书--------------------------------------------\n");
	printf("-------------------------------依据标题依次输入(信息之间空格)---------------------------------\n");
	printf("%s\n", Title);
	scanf("%d%s%s%s%s%d%f", &value.ID, value.Class, value.BookName, value.Author, value.Publishing, &value.Count, &value.Price);

	//判断是不是已存在的书籍
	ListNode* Node = ListFind(pHead, pHead, value.BookName);//通过书名查找该书籍
	//该名书籍存在且各信息相同
	if (Node)//如果重复则数量加1即可
	{
		if (strcmp(Node->data.Class, value.Class) == 0 && strcmp(Node->data.Author, value.Author) == 0 && strcmp(Node->data.Publishing, value.Publishing) == 0 && Node->data.Price == value.Price)
		{
			++(Node->data.Count);
			return;
		}
	}
	ListInsert(insertpos, value);
	++(pHead->data.Count);
}

//删除书籍-单个删除/批量删除
void EraseBook(ListNode* pHead)
{
	printf("1.指定编号删除\n2.文献批量删除\n(输入其他任意数字退出!)\n");
	printf("请选择>");
	int order = -1;
	scanf("%d", &order);
	ListNode* earsepos = NULL;
	if (order == 1)
	{
		int id = -1;
		printf("请输入删除书籍的编号>");
		scanf("%d", &id);
        ListNode* cur = NULL;
		for (cur = pHead->next; cur != pHead; cur = cur->next)//查找编号
		{
			if (cur->data.ID == id)
			{
				earsepos = cur;
				break;
			}
		}
		if (earsepos)
		{
			ListErase(earsepos);
			--(pHead->data.Count);
		}
	}
	else if (order == 2)
	{
		char bookname[50];
		printf("请输入删除书籍的书名或作者或出版社或分类>");
		scanf("%s", bookname);
		ListNode* cur = pHead;
		earsepos = pHead;
		while (cur)
		{
			cur = ListFind(pHead, earsepos, bookname);
			if (cur)
			{
				earsepos = cur->prev;//保持节点的上一个下次从节点的上一个开始
				ListErase(cur);
				--(pHead->data.Count);
			}
		}
	}
}


void ChangeInf(ListNode* pHead)//修改信息-更新
{
	printf("1.按编号查询修改\n2.按书名查询修改\n(其他数字退出修改!)\n\n请选择>");
	int order = -1;
	scanf("%d", &order);
	ListNode* changepos = NULL;//要修改的书籍的地址
	if (order == 1)
	{
		int id = -1;
		printf("请输入修改书籍的当前编号>");
		scanf("%d", &id);
        ListNode* cur = NULL;
		for (cur = pHead->next; cur != pHead; cur = cur->next)//查找编号
		{
			if (cur->data.ID == id)
			{
				changepos = cur;
				break;
			}
		}
	}
	else if(order == 2)
	{
		char bookname[50];
		printf("请输入修改书籍的当前书名>");
		scanf("%s", bookname);
		changepos = ListFind(pHead, pHead, bookname);//查询书籍获得地址
	}

	if (changepos)
	{
		system("cls");
		printf("----------------------------------------将修改的书籍------------------------------------------\n");
		printf("%s\n", Title);
		printf("%-6d %-10s %-20s %-10s %-30s %-6d %-2.2f\n", changepos->data.ID, changepos->data.Class, changepos->data.BookName, changepos->data.Author, changepos->data.Publishing, changepos->data.Count, changepos->data.Price);
		printf("\n*1.修改书籍编号*\n*2.修改书籍分类*\n*3.修改书籍书名*\n*4.修改书籍作者*\n*5.修改书籍出版社*\n*6.修改书籍数量*\n*7.修改书籍单价*\n*0.放弃修改信息*\n\n请选择>");
		int order = -1;
		scanf("%d", &order);
		switch (order)
		{
			case 1: 
			{
				printf("请输入新的编号>");
				scanf("%d", &(changepos->data.ID));
				break;
			}
			case 2:
			{
				printf("请输入新的分类类名>");
				scanf("%s", changepos->data.Class);
				break;
			}
			case 3:
			{
				printf("请输入新的书名>");
				scanf("%s", changepos->data.BookName);
				break;
			}
			case 4:
			{
				printf("请输入新的作者名>");
				scanf("%s", changepos->data.Author);
				break;
			}
			case 5:
			{
				printf("请输入新的出版社名>");
				scanf("%s", changepos->data.Publishing);
				break;
			}
			case 6:
			{
				printf("请输入新的数量>");
				scanf("%d", &(changepos->data.Count));
				break;
			}
			case 7:
			{
				printf("请输入新的单价>");
				scanf("%f", &(changepos->data.Price));
				break;
			}
			default: {break; }
		}
	}
}


ListNode* NodeLookUP(ListNode* pHead, int n)//交换
{
	ListNode* cur = pHead->prev;
	while (n--)
	{
		cur = cur->prev;
	}
	return cur;
}

void InsertSortBookID(ListNode* pHead)//插入排序-对编号进行排序
{
	printf("(1)升序(2)降序(其他数字)放弃排序>");
	int order = -1;
	scanf("%d", &order);
	if (order == 1)
	{
        int i = 0;
		for (; i < (pHead->data.Count) - 1; ++i)
		{
			int end = i;
			ListNode* tmp = NodeLookUP(pHead, i + 1);
			ListNode* endi = NULL;
			ElemType keyi = tmp->data;//先保存待插入值
			while (end >= 0)
			{
				endi = NodeLookUP(pHead, end);//插入的末尾
				if (endi->data.ID > keyi.ID)
				{
					tmp->data = endi->data;
					tmp = endi;
				}
				--end;
			}
			tmp->data = keyi;
		}
	}
	else if(order == 2)
	{
        int i = 0;
		for (; i < (pHead->data.Count) - 1; ++i)
		{
			int end = i;
			ListNode* tmp = NodeLookUP(pHead, i + 1);
			ListNode* endi = NULL;
			ElemType keyi = tmp->data;//先保存待插入值
			while (end >= 0)
			{
				endi = NodeLookUP(pHead, end);//插入的末尾
				if (endi->data.ID < keyi.ID)
				{
					tmp->data = endi->data;
					tmp = endi;
				}
				--end;
			}
			tmp->data = keyi;
		}
	}
	
}


void ShellSortBookCount(ListNode* pHead)//希尔排序-对数量进行排序
{
	printf("(1)升序(2)降序(其他数字)放弃排序>");
	int order = -1;
	scanf("%d", &order);
	if (order == 1)
	{
		int Step = pHead->data.Count;
		while (Step > 1)
		{
			Step = (Step / 3) + 1;
            int i = 0;
			for ( ;i < (pHead->data.Count) - Step; ++i)
			{
				int end = i;
				ListNode* tmp = NodeLookUP(pHead, i + 1);
				ListNode* endi = NULL;
				ElemType keyi = tmp->data;//先保存待插入值
				while (end >= 0)
				{
					endi = NodeLookUP(pHead, end);//插入的末尾
					if (endi->data.Count > keyi.Count)
					{
						tmp->data = endi->data;
						tmp = endi;
					}
					end -= Step;
				}
				tmp->data = keyi;
			}
		}
	}
	else if (order == 2)
	{
		int Step = pHead->data.Count;
		while (Step > 1)
		{
			Step = (Step / 3) + 1;
            int i = 0;
			for (; i < (pHead->data.Count) - Step; ++i)
			{
				int end = i;
				ListNode* tmp = NodeLookUP(pHead, i + 1);
				ListNode* endi = NULL;
				ElemType keyi = tmp->data;//先保存待插入值
				while (end >= 0)
				{
					endi = NodeLookUP(pHead, end);//插入的末尾
					if (endi->data.Count < keyi.Count)
					{
						tmp->data = endi->data;
						tmp = endi;
					}
					end -= Step;
				}
				tmp->data = keyi;
			}
		}
	}
}

int GetRandMidIndex(ListNode* pHead, int head, int end)//随机三数取中
{
	srand((time_t)time(NULL));
	int mid = head + rand() % (end - head);
	float left = NodeLookUP(pHead, head)->data.Price;
	float midi = NodeLookUP(pHead, mid)->data.Price;
	float right = NodeLookUP(pHead, end)->data.Price;
	if (left > midi)
	{
		if (midi > right)
		{
			return mid;
		}
		else
		{
			if (left > right)
			{
				return end;
			}
			else
			{
				return head;
			}
		}
	}
	else
	{
		if (midi > right)
		{
			if (left > right)
			{
				return head;
			}
			else
			{
				return end;
			}
		}
		else
		{
			return mid;
		}
	}
}

void QuickSortBookPriceAsc(ListNode* pHead,int Head,int End)//快速排序-对价格进行排序-升序
{
	
	if (Head >= End)//递归到最后停止
		return;

	if ((End - Head + 1) <= 10)//当排序数据量小于10时使用插入排序减小栈的使用
	{
        int i = Head;
		for (; i < End; ++i)
		{
			int end = i;
			ListNode* tmp = NodeLookUP(pHead, i + 1);
			ListNode* endi = NULL;
			ElemType keyi = tmp->data;//先保存待插入值
			while (end >= 0)
			{
				endi = NodeLookUP(pHead, end);//插入的末尾
				if (endi->data.Price > keyi.Price)
				{
					tmp->data = endi->data;
					tmp = endi;
				}
				--end;
			}
			tmp->data = keyi;
		}
	}
	else
	{
		int head = Head;
		int end = End;
		int cur = head + 1;
		Swap(&(NodeLookUP(pHead, head)->data), &(NodeLookUP(pHead, GetRandMidIndex(pHead, Head, End))->data));//三数取中，取一个中等大小的数插入表头
		ListNode* keyi = NodeLookUP(pHead, head);
		ListNode* left = NodeLookUP(pHead, head);
		ListNode* right = NodeLookUP(pHead, end);
		ListNode* curi = NodeLookUP(pHead, cur);
		//三路并排
		while (cur <= end)
		{
			if (curi->data.Price < keyi->data.Price)
			{
				Swap(&(curi->data), &(left->data));
				++cur;
				++head;
			}
			else if (curi->data.Price > keyi->data.Price)
			{
				Swap(&(curi->data), &(right->data));
				--end;
			}
			else if (curi->data.Price == keyi->data.Price)
			{
				++cur;
			}
			curi = NodeLookUP(pHead, cur);
			left = NodeLookUP(pHead, head);
			right = NodeLookUP(pHead, end);
		}
		QuickSortBookPriceAsc(pHead, Head, head - 1);
		QuickSortBookPriceAsc(pHead, end + 1, End);
	}
}

void QuickSortBookPriceDes(ListNode* pHead, int Head, int End)//快速排序-对价格进行排序-降序
{

	if (Head >= End)//递归到最后停止
		return;

	if ((End - Head + 1) <= 10)//当排序数据量小于10时使用插入排序减小栈的使用
	{
        int i = Head;
		for (; i < End; ++i)
		{
			int end = i;
			ListNode* tmp = NodeLookUP(pHead, i + 1);
			ListNode* endi = NULL;
			ElemType keyi = tmp->data;//先保存待插入值
			while (end >= 0)
			{
				endi = NodeLookUP(pHead, end);//插入的末尾
				if (endi->data.Price < keyi.Price)
				{
					tmp->data = endi->data;
					tmp = endi;
				}
				--end;
			}
			tmp->data = keyi;
		}
	}
	else
	{
		int head = Head;
		int end = End;
		int cur = head + 1;
		Swap(&(NodeLookUP(pHead, head)->data), &(NodeLookUP(pHead, GetRandMidIndex(pHead, Head, End))->data));//三数取中，取一个中等大小的数插入表头
		ListNode* keyi = NodeLookUP(pHead, head);
		ListNode* left = NodeLookUP(pHead, head);
		ListNode* right = NodeLookUP(pHead, end);
		ListNode* curi = NodeLookUP(pHead, cur);
		//三路并排
		while (cur <= end)
		{
			if (curi->data.Price > keyi->data.Price)
			{
				Swap(&(curi->data), &(left->data));
				++cur;
				++head;
			}
			else if (curi->data.Price < keyi->data.Price)
			{
				Swap(&(curi->data), &(right->data));
				--end;
			}
			else if (curi->data.Price == keyi->data.Price)
			{
				++cur;
			}
			curi = NodeLookUP(pHead, cur);
			left = NodeLookUP(pHead, head);
			right = NodeLookUP(pHead, end);
		}
		QuickSortBookPriceDes(pHead, Head, head - 1);
		QuickSortBookPriceDes(pHead, end + 1, End);
	}
}

void BubbleSortBookClass(ListNode* pHead)//对类名进行冒泡排序
{
	assert(pHead);
	ListNode* end = pHead->prev;
	bool flag = true;
    ListNode* cur = NULL;
	for (cur = pHead->next; cur != pHead; cur = cur->next)
	{
        ListNode* curr = NULL;
		for (curr = pHead->next; curr != end; curr = curr->next)
		{
			if (strcmp(curr->data.Class, curr->next->data.Class) < 0)
			{
				Swap(&curr->data, &curr->next->data);
				flag = false;
			}
		}
		if (flag)
		{
			break;
		}
		end = end->prev;
	}
}

void BubbleSortBookPub(ListNode* pHead)//对出版社进行冒泡排序
{
	assert(pHead);
	ListNode* end = pHead->prev;
	bool flag = true;
    ListNode* cur = NULL;
	for (cur = pHead->next; cur != pHead; cur = cur->next)
	{
        ListNode* curr = NULL;
		for (curr = pHead->next; curr != end; curr = curr->next)
		{
			if (strcmp(curr->data.Publishing, curr->next->data.Publishing) < 0)
			{
				Swap(&curr->data, &curr->next->data);
				flag = false;
			}
		}
		if (flag)
		{
			break;
		}
		end = end->prev;
	}
}

void BookSort(ListNode* pHead)//图书排序
{
	printf("(1)对编号进行插入排序\n(2)对数量进行希尔排序\n(3)对价格进行快速排序\n(4)对类名进行冒泡排序\n(5)对出版社进行冒泡排序\n(其他数字放弃排序！)\n请选择>");
	int order = -1;
	scanf("%d", &order);
	switch (order)
	{
		case 1:
		{
			InsertSortBookID(pHead);
			break;
		}
		case 2:
		{
			ShellSortBookCount(pHead);
			break;
		}
		case 3:
		{
			printf("(1)升序(2)降序(其他数字)放弃排序>");
			int order = -1;
			scanf("%d", &order);
			if (order == 1)
			{
				QuickSortBookPriceAsc(pHead, 0, (pHead->data.Count) - 1);
			}
			else if (order == 2)
			{
				QuickSortBookPriceDes(pHead, 0, (pHead->data.Count) - 1);
			}
		}
		case 4:
		{
			BubbleSortBookClass(pHead);
			break;
		}
		case 5:
		{
			BubbleSortBookPub(pHead);
			break;
		}
		default: {break; }
	}
}